문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 블룸 필터 (문단 편집) == 개념 == [[파일:external/upload.wikimedia.org/649px-Bloom_filter.svg.png]] [[http://en.wikipedia.org/wiki/Bloom_filter|(위키백과, 영어 주의)]] 어떤 값을 여러 해시 함수에 넣어 결과값들을 임의의 테이블에 인덱싱하여 해당되는 모든 값이 1인지를 따지는 자료구조. 해시 함수는 기본적으로 충돌의 가능성이 있기에 블룸 필터에는 긍정 오류(false positive)[* 쉽게 말해 넣은 적 없는 값에 대해 있다고 하는 경우. 그 반대인 부정 오류는 넣은 적 있는데 없다고 하는 경우이다.]의 가능성이 있다. 다만 반대로 부정 오류(false negative)의 가능성은 없다. 즉, 해당 값이 테이블 내 확률적으로 있거나 절대로 없음을 확인할 수 있다. 해시 함수들을 기본적으로 여러 개를 가지는데 임의의 테이블의 크기, 넣어야 하는 자료의 크기, 해시 함수의 수에 따라 오류의 확률이 정해진다. 그래서 요구하는 긍정 오류율이 있다면 넣어야 하는 자료의 크기를 고려해서 테이블의 크기와 해시 함수의 수를 정하는 편이다. 여기까지 읽었으면 알겠지만 있는지 없는지만을 보는 그 특성 때문에 삽입만 가능하고 '''제거가 안 된다.'''(...) 위의 그림에서 보다시피 여러 값이 똑같은 인덱스에 대응될 수 있기 때문에 어떤 저장된 값을 제거하기 위해 해당 값에 대응되는 인덱스의 요소들을 0으로 만들어버리면 기존에 저장되어있던 다른 값들에 영향을 미치게 되기 때문이다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기